package com.xzz.lfu;



import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * @author: hhz
 * @create: 2021-12-23 11:01
 **/
public class LFUCache {
    // key 到 val 的映射，我们后文称为 KV 表
    HashMap<Integer, Integer> keyToVal;
    // key 到 freq 的映射，我们后文称为 KF 表
    HashMap<Integer, Integer> keyToFreq;
    // freq 到 key 列表的映射，我们后文称为 FK 表
    HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
    // 记录最小的频次
    int minFreq;
    // 记录 LFU 缓存的最大容量
    int cap;
    class Node<K,V>{
        K key;
        V value;
        Node<K,V> prev;//前一个
        Node<K,V> next;//后一个
        Node(){}
        Node(K key,V value){
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }
    }
    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        this.cap = capacity;
        this.minFreq = 0;
    }

    public int get(int key) {
        if(!keyToVal.containsKey(key)){
            return -1;
        }
        Integer val = keyToVal.get(key);
        //增加该key的使用次数+1
        addFreq(key);
        return val;
    }
    private void addFreq(int key){
        Integer freq = keyToFreq.get(key);
        keyToFreq.put(key,freq+1);
        freqToKeys.get(freq).remove(key);
        freqToKeys.putIfAbsent(freq+1,new LinkedHashSet<>());
        freqToKeys.get(freq+1).add(key);

        //加完之后 原先的freq对应的keySet如果空了
        LinkedHashSet<Integer> keys = freqToKeys.get(freq);
        if(keys.isEmpty()){
            freqToKeys.remove(freq);
            //如果这个freq刚好就是最小的 现在干掉了 自然minFreq也要自增
            if(minFreq == freq){
                minFreq++;
            }
        }
    }
    public void put(int key, int val) {
        if (this.cap <= 0) return;
        if(keyToVal.containsKey(key)){
            keyToVal.put(key,val);
            addFreq(key);
        }else {
            if(keyToVal.size() >= cap){
                this.removeMinFreq();
            }
            keyToVal.put(key,val);
            keyToFreq.put(key,1);
            freqToKeys.putIfAbsent(1,new LinkedHashSet<>());
            freqToKeys.get(1).add(key);
            this.minFreq=1;
        }
    }
    private void removeMinFreq(){
        LinkedHashSet<Integer> keys = freqToKeys.get(minFreq);
        //第一个就是 最久的
        Integer deleteKey = keys.iterator().next();
        keys.remove(deleteKey);
        //如果删除了后 空了 那么这个维护也没用了
        if(keys.isEmpty()){
            freqToKeys.remove(minFreq);
            //这里不需要更新minFreq的值  因为 removeMinFreq 在put方法中 如果 put了新的key 则minFreq =1 如果put了已有的key 则minFreq也会自增
        }
        keyToVal.remove(deleteKey);
        keyToFreq.remove(deleteKey);
    }
    public static void main(String[] args) {
//        LFUCache  lFUCache = new LFUCache(2);
//        lFUCache.put(1, 1);   // cache=[1,_], cnt(1)=1
//        lFUCache.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
//        lFUCache.get(1);      // 返回 1
//        // cache=[1,2], cnt(2)=1, cnt(1)=2
//        lFUCache.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
//        // cache=[3,1], cnt(3)=1, cnt(1)=2
//        lFUCache.get(2);      // 返回 -1（未找到）
//        lFUCache.get(3);      // 返回 3
//        // cache=[3,1], cnt(3)=2, cnt(1)=2
//        lFUCache.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
//        // cache=[4,3], cnt(4)=1, cnt(3)=2
//        lFUCache.get(1);      // 返回 -1（未找到）
//        lFUCache.get(3);      // 返回 3
//        // cache=[3,4], cnt(4)=1, cnt(3)=3
//        lFUCache.get(4);      // 返回
        LFUCache  lFUCache = new LFUCache(0);
        lFUCache.put(0,0);
        lFUCache.get(0);

    }
}
